package tree

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/
// 二叉树的最大深度
// 算法: 通过 stack 遍历 / 递归
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func MaxDepth(root *TreeNode) int {
	if nil == root {
		return 0
	}
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	depth := 0
	hasNodeNotEmpty := true
	for len(stack) > 0 && hasNodeNotEmpty {
		currentSize := len(stack)
		// 遍历当前这层的所有数据
		// 注意如果所有节点都是nil，直接跳出循环
		hasNodeNotEmpty = false
		depth++
		for currentSize > 0 {
			currentNode := stack[0]
			if len(stack) > 1 {
				stack = stack[1:]
			} else {
				stack = []*TreeNode{}
			}
			currentSize--
			if currentNode == nil {
				continue
			}
			hasNodeNotEmpty = true
			leftNode := currentNode.Left
			rightNode := currentNode.Right
			stack = append(stack, leftNode)
			stack = append(stack, rightNode)
		}
		if !hasNodeNotEmpty {
			depth--
		}
	}
	return depth
}
